Communications networks are formed of a number of network elements (NEs) interconnected by links. The links interconnecting the NEs may follow one of a number of predefined schemes, resulting in various network topologies, such as ring, star, linear, and full-mesh topologies. It is further commonplace in today's networks to find different autonomously managed networks bridged to each other at various gateways, and for data transport services to be provided across the networks in a manner that is transparent to users.
Typically, core networks receive traffic from edge networks, the core network providing interconnection between disparate edge networks, and generally providing longer haul data transport. In recent years for numerous reasons, including security, privacy, scalability, and especially for simplicity in making routing decisions, core network providers have begun presenting abstracted representations of the topologies of their core networks to edge network NEs. Generally, the core network is abstracted to represent a full mesh network (so that each abstracted NE is linked to each other abstracted NE). Such an abstracted network typically includes only the NEs relevant to the edge network, which may be every core NE that is liked to an edge network NE, or a subset of these core NEs.
As noted, one of the reasons for presenting the abstracted view of the core network is that routing decisions required by the edge networks are simplified. For example, many core networks have a ring topology, such as a synchronous optical network (SONET) ring, and many of those ring networks impose timeslot continuity restrictions on allowable paths. Timeslot continuity is a requirement that traffic conveyed over successive links of the ring must occupy the same timeslot on adjacent links. Where timeslot continuity is not available, traffic cannot be routed through the adjacent links in sequence, even though each link, taken alone, has sufficient capacity to carry the traffic. Such a problem introduces a constraint in computing routes through the abstracted core, because it is possible that capacity is available over a link ab between A and B, and a link bc between B and C, but traffic cannot transit ab and then bc in sequence. Such a constraint is termed “subset intransitivity”, because transitivity (a well known mathematical property of binary relations asserting that for any a, b, c, if a is related to b, and b is related to c, then a is related to c) of the network fails if each of routes ab and bc are individually allowable but route abc (that is, routes ab and bc in sequence) is not allowable, in the same subnetwork.
Similar subset intransitivity is encountered in passive optical networks where wavelength continuity is required. In passive optical networks no optical fiber link of the passive optical network can transport two channels of a same wavelength. Accordingly a wavelength channel may be available on a first optical fiber link, and a second wavelength channel may be available on an adjacent link, but it is not possible to transmit a signal over both links in sequence.
Presenting the full-mesh abstracted topology therefore presents a new class of constrained routing problems for the edge network elements. Correctly identifying allowable routes is of high importance because every failed request constitutes a loss of processor time and congests network control channels.
While numerous methods for computing routes using Dijkstra's algorithm and a plurality of weights that resolve certain constraints, and using various techniques (artificial intelligence applications, and linear programming methods, etc.) are known, none of these methods can compute paths that are guaranteed to be optimum allowable paths subject to a subset intransitivity constraint.
Consequently, there remains a need for an abstraction of a physical network that introduces subset intransitivity that can be used for computing routes, so that edge network elements can be provided with a simplified representation of the network that is accurate for the routing requirements of the edge network element.